class Solution:
    def updateMatrix(self, matrix):
        xlen = len(matrix)
        ylen = len(matrix[0])
        stack = set()
        nowLen = [[None for _ in range(ylen)] for _ in range(xlen)]
        for i in range(xlen):
            for j in range(ylen):
                if matrix[i][j] == 1:
                    m, nextPoints = self.minLen(matrix, xlen, ylen, nowLen, i, j)
                    if m == 1:
                        nowLen[i][j] = m
                        stack.add((i, j))
                else:
                    nowLen[i][j] = 0
        while len(stack):
            tmp = set()
            while len(stack):
                x, y = stack.pop()
                m, nextPoints = self.minLen(matrix, xlen, ylen, nowLen, x, y)
                nowLen[x][y] = m
                tmp = tmp.union(nextPoints)
            stack = tmp
        return nowLen

    def minLen(self, matrix, xLen, yLen, nowLen, x, y):
        m = None
        nextPoints = set()
        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < xLen and 0 <= j < yLen:
                if matrix[i][j] == 0:
                    m = 1
                    continue
                elif nowLen[i][j] is None:
                    nextPoints.add((i, j))
                    continue
                else:
                    if m is None:
                        m = nowLen[i][j]+1
                    else:
                        m = min(m, nowLen[i][j]+1)
        return m, nextPoints


if __name__ == '__main__':
    so = Solution()
    s = """
0 0 0
0 1 0
1 1 1"""
    s = s[1:]
    s = s.split("\n")
    s = [x.split(" ") for x in s]
    s = [[int(y) for y in x] for x in s]
    print(s)
    r = so.updateMatrix(s)
    print(r)
